package com.peng.leetcode.unionFind;

/**
 * ValidateBinaryTreeNodes
 * <p>
 * 1361. 验证二叉树
 *
 * @author: lupeng6
 * @create: 2021/3/1 10:58
 */
public class ValidateBinaryTreeNodes {

    public static void main(String[] args) {

    }


    /**
     * 使用并查集验证 图的连通性
     *
     * @author lupeng6
     * @date 2021/3/1 10:58
     */
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        // 并查集
        this.parent = new int[n + 1];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < n; i++) {
            int left = leftChild[i];
            int right = rightChild[i];

            int root = find(i);
            if (left != -1) {
                int root1 = find(left);
                if (root != root1) {
                    parent[root] = root1;
                } else {
                    return false;
                }
            }

            if (right != -1) {
                int root1 = find(right);
                if (root != root1) {
                    parent[root] = root1;
                } else {
                    return false;
                }
            }
        }

        return true;
    }

    private int[] parent;

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }



}
